package _3sort.src;


/**
 * @className: mergeSort
 * @description:
 * @author: myself
 * @date: 2025/7/15 17:43
 * @version: 0.1
 * @since: JDK17
 */
//归并排序是一种基于分治法的高效排序算法。它将一个大的列表分成两个较小的子列表，
// 然后递归地对每个子列表进行排序，最后合并这两个已排序的子列表以产生最终排序的结果。
// 归并排序的关键在于其稳定性和效率，在最坏情况下的时间复杂度为O(nlog n)，这里n是元素的数量
//时间复杂度：O(nlogn)，空间复杂度O（n）
public class _4mergeSort {
    public static void process(int[] nums, int n, int m) {
        if (n == m) {
            return;
        }
        int mid=(n+m)>>>1;//获取中间值，无符号右移一位
        process(nums, n, mid);
        process(nums, mid + 1, m);
        merge(nums, n, mid, m);
    }

    public static void merge(int[] nums, int n, int m, int l) {
        int[] temp = new int[l - n + 1];//创建一个空白数组，用于转移
        int p1=n;
        int p2=m+1;
        int i=0;
        while (p1<=m&&p2<=l) {
            temp[i++]=nums[p1]<=nums[p2]?nums[p1++]:nums[p2++];//判断添加谁
        }
        while (p1 <= m) {
            temp[i++] = nums[p1++];
        }
        while (p2 <= l) {
            temp[i++] = nums[p2++];
        }
        System.arraycopy(temp,0,nums,n,temp.length);//用于数组的copy，在这里的参数要注意
    }
    public static void main(String[] args) {
        int[] nums = {2, 5, 6, 3, 1,7, 4, 9, 8};
        process(nums,0,nums.length-1);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }
}
